class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        bit = len(str(n))  # 一共需要找多少个不同的数
        return (n + 1) - self.dfs(bit, n, [])

    def dfs(self, bit, n, lst):
        """ 寻找不包含相同的数的选择数量

        :param bit: 还需要找多少个不同的数
        :param n: 要找的这些数必须小于等于n
        :param lst: 不能使用的数字
        :return: 选择数量
        """
        # 还需要找0个不同的数
        if bit == 0:
            print("DFS:", n, lst, "->", 0)
            return 0

        # 还需要找1个不同的数
        elif bit == 1:
            ans = 0
            for i in range(n + 1):
                if i not in lst:
                    ans += 1
            print("DFS:", n, lst, "->", ans)
            return ans

        # 还需要找1个以上不同的数
        else:
            ans = 0
            first = int(str(n).zfill(bit)[0])
            back = int(str(n).zfill(bit)[1:])

            # 遍历最后1个选择的选择
            for i in range(first):
                # 如果当前还没有第1位，则选择0的话不计入不可使用的数列表
                if not lst and i == 0:
                    ans += self.dfs(bit - 1, pow(10, bit - 1) - 1, [])

                # 如果当前已经有了第1位
                elif i not in lst:
                    ans += self.dfs(bit - 1, pow(10, bit - 1) - 1, lst + [i])

            # 处理最后1个选择
            ans += self.dfs(bit - 1, back, lst + [first])

            print("DFS:", n, lst, "->", ans)

            return ans


if __name__ == "__main__":
    print(Solution().numDupDigitsAtMostN(20))  # 1
    print(Solution().numDupDigitsAtMostN(100))  # 10
    print(Solution().numDupDigitsAtMostN(121))  # 22
    print(Solution().numDupDigitsAtMostN(1000))  # 262

    # 测试用例62/129
    print(Solution().numDupDigitsAtMostN(1))  # 0

    # 测试用例63/129
    print(Solution().numDupDigitsAtMostN(9))  # 0

    # 测试用例64/129
    print(Solution().numDupDigitsAtMostN(110))  # 12

    # 测试用例69/129
    print(Solution().numDupDigitsAtMostN(1962))  # 739
